package Day2025_02_28;

public class LeetCode493 {
    int[] tmpNums;
    public int reversePairs(int[] nums) {
        int n = nums.length;
        tmpNums = new int[n];
        return mergeSort(nums, 0, n - 1);
    }
    private int mergeSort (int[] nums, int left, int right) {
        if (left >= right) return 0;
        int ret = 0;
        int mid = (left + right) / 2;
        ret += mergeSort(nums, left, mid);
        ret += mergeSort(nums, mid + 1, right);
        int cur1 = left, cur2 = mid + 1, i = left;
//        while (cur2 <= right) {
//            if (cur1 <= mid && nums[cur1] / 2.0 > nums[cur2]) {
//                ret += right - cur2 + 1;
//                cur1++;
//            }
//            if (cur1 > mid) break;
//            if (nums[cur1] / 2.0 <= nums[cur2]) cur2++;
//        }
        while (cur1 <= mid) {
            while (cur2 <= right && nums[cur2] >= nums[cur1] / 2.0) cur2++;
            if (cur2 > right) break;
            ret += right - cur2 + 1;
            cur1++;
        }
        int s1 = left, e1 = mid;
        int s2 = mid + 1, e2 = right;
        int k = left;
        while (s1 <= e1 && s2 <= e2) tmpNums[k++] = nums[s1] > nums[s2] ? nums[s1++] : nums[s2++];
        while (s1 <= e1) tmpNums[k++] = nums[s1++];
        while (s2 <= e2) tmpNums[k++] = nums[s2++];
        for (int j = left; j <= right; j++) nums[j] = tmpNums[j];
        return ret;
    }
}
